package com.yulongtian.weekCompetition.month202211.week4;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 单调栈
 * 可
 *
 * @author yulongTian
 * @create 2022-11-27 10:55
 */
public class Test03 {
    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        ListNode root1 = new ListNode(1);
        ListNode root2 = new ListNode(1);
        ListNode root3 = new ListNode(1);
        root.next = root1;
        root1.next = root2;
        root2.next = root3;

        removeNodes(root);

    }

    public static ListNode removeNodes(ListNode head) {

        Deque<ListNode> stack = new LinkedList<>();

        ListNode point = head;
        while (point != null) {
            if (stack.isEmpty()) {
                ListNode temp = new ListNode(point.val);
                temp.next = null;
                stack.push(temp);
                point = point.next;
                continue;
            }

            //不为空 且大于  出栈
            while (!stack.isEmpty() && point.val > stack.peek().val) {
                stack.pop();
            }

            //不为空  且小于等于 入栈
            while (!stack.isEmpty() && point != null && point.val <= stack.peek().val) {
                ListNode temp = new ListNode(point.val);
                temp.next = null;
                stack.push(temp);
                point = point.next;
            }
        }

        //转移到另一个栈
        Deque<ListNode> tempStack = new LinkedList<>();
        while (!stack.isEmpty()) {
            tempStack.push(stack.pop());
        }

        head = tempStack.pop();
        point = head;

        while (!tempStack.isEmpty()) {
            point.next = tempStack.pop();
            point = point.next;
        }


        return head;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
